---
title: "9、GCD王国和LCM王国"
created: 2025-11-28
tags:
  - 算法
---

# 9、GCD王国和LCM王国

## 题目 [GCD王国和LCM王国](https://www.lanqiao.cn/problems/3137/learning/)

![[image-66c63f2c.png]]

## 思路分析

最大公因数 gcd 辗转相除 return b?gcd(b,a%b):a

最小公倍数lcm a\*b/gcd(a,b)

我直接照公式敲 模拟 过了9/15

还有个逆天的操作 直接算gcd居然可以全过 只能说蓝桥杯的数据太水了

正解好像是要什么数学推导 反着求……

考试想不到的 这种题目 靠后的 能水就水 能模拟就模拟 把一定能拿到的分拿到

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=1e5+10;

LL a[N];

vector<LL> s;

LL gcd(LL a,LL b){

	return b?gcd(b,a%b):a;

}

LL lcm(LL a,LL b){

	return (a*b)/gcd(a,b);

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n;cin>>n;

    for(int i=0;i<n;i++)

    	cin>>a[i];

    for(int i=0;i+1<n;i++)

    	s.push_back(lcm(a[i],a[i+1]));

	LL ans=0;

	for(int i=0;i<s.size();i++)

		ans=gcd(ans,s[i]);

	cout<<ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[8、完美队列的数目|8、完美队列的数目]] 🏠 [[00-刷题理模型]] ➡️ [[十五届省赛冲刺营结营考试|十五届省赛冲刺营结营考试]]